// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include <limits.h>
// #include"windows.h"
//
// #define MaxVertexNum 100 // 最大顶点数
//
// typedef char VertexType; // 顶点数据类型
//
// // 边表节点
// typedef struct ArcNode {
//     int adjvex;          // 该弧指向的顶点位置
//     struct ArcNode* next; // 指向下一条弧的指针
// } ArcNode;
//
// // 顶点表节点
// typedef struct VNode {
//     VertexType data;    // 顶点信息
//     ArcNode* first;     // 指向第一条依附该顶点的弧的指针
// } VNode, AdjList[MaxVertexNum];
//
// // 邻接表图结构
// typedef struct {
//     AdjList vertices; // 邻接表
//     int vexnum, arcnum; // 顶点数和边数
// } ALGraph;
//
// // 初始化邻接表图
// void InitALGraph(ALGraph* G) {
//     G->vexnum = 0;
//     G->arcnum = 0;
//     for (int i = 0; i < MaxVertexNum; i++) {
//         G->vertices[i].first = NULL;
//     }
// }
//
// // 添加顶点到邻接表图
// void AddVertexAL(ALGraph* G, VertexType v) {
//     if (G->vexnum < MaxVertexNum) {
//         G->vertices[G->vexnum].data = v;
//         G->vexnum++;
//     }
// }
//
// // 添加边到邻接表图
// void AddEdgeAL(ALGraph* G, int v1, int v2) {
//     if (v1 >= 0 && v1 < G->vexnum && v2 >= 0 && v2 < G->vexnum) {
//         ArcNode* newNode = (ArcNode*)malloc(sizeof(ArcNode));
//         newNode->adjvex = v2;
//         newNode->next = G->vertices[v1].first;
//         G->vertices[v1].first = newNode;
//
//         // 无向图需要对称赋值
//         newNode = (ArcNode*)malloc(sizeof(ArcNode));
//         newNode->adjvex = v1;
//         newNode->next = G->vertices[v2].first;
//         G->vertices[v2].first = newNode;
//
//         G->arcnum++;
//     }
// }
//
// // BFS 单源最短路径
// void BFSShortestPath(ALGraph* G, int start) {
//     if (start < 0 || start >= G->vexnum) {
//         printf("错误：起始顶点编号超出范围！\n");
//         return;
//     }
//
//     // 初始化距离数组和路径数组
//     int distance[MaxVertexNum]; // 存储从 start 到每个顶点的最短距离
//     int path[MaxVertexNum];     // 存储从 start 到每个顶点的路径上的前驱顶点
//     for (int i = 0; i < G->vexnum; i++) {
//         distance[i] = INT_MAX; // 初始化为无穷大
//         path[i] = -1;          // 初始化为 -1，表示没有前驱
//     }
//
//     // 使用队列实现 BFS
//     int queue[MaxVertexNum]; // 简单队列
//     int front = 0, rear = 0; // 队头和队尾指针
//
//     // 初始化起始顶点
//     distance[start] = 0; // 起始顶点到自身的距离为 0
//     path[start] = start; // 起始顶点的前驱是自身
//     queue[rear++] = start; // 入队
//
//     while (front < rear) {
//         int v = queue[front++]; // 出队
//         ArcNode* p = G->vertices[v].first;
//
//         // 遍历 v 的所有邻接点
//         while (p != NULL) {
//             int w = p->adjvex; // w 是 v 的邻接点
//             if (distance[w] == INT_MAX) { // 如果 w 未被访问过
//                 distance[w] = distance[v] + 1; // 更新距离
//                 path[w] = v; // 记录路径
//                 queue[rear++] = w; // 入队
//             }
//             p = p->next;
//         }
//     }
//
//     // 输出最短路径和距离
//     printf("从顶点 %c 到其他顶点的最短路径和距离：\n", G->vertices[start].data);
//     for (int i = 0; i < G->vexnum; i++) {
//         if (i == start) continue; // 跳过起始顶点
//
//         printf("到顶点 %c 的最短距离: %d，路径: ", G->vertices[i].data, distance[i]);
//
//         // 输出路径
//         int current = i;
//         while (current != start) {
//             printf("%c <- ", G->vertices[current].data);
//             current = path[current];
//         }
//         printf("%c\n", G->vertices[start].data);
//     }
// }
//
// int main() {
//     SetConsoleOutputCP(CP_UTF8);
//     ALGraph G;
//     InitALGraph(&G);
//
//     // 添加顶点
//     AddVertexAL(&G, 'A');
//     AddVertexAL(&G, 'B');
//     AddVertexAL(&G, 'C');
//     AddVertexAL(&G, 'D');
//     AddVertexAL(&G, 'E');
//
//     // 添加边
//     AddEdgeAL(&G, 0, 1); // A-B
//     AddEdgeAL(&G, 0, 2); // A-C
//     AddEdgeAL(&G, 1, 3); // B-D
//     AddEdgeAL(&G, 2, 4); // C-E
//
//     // 执行 BFS 单源最短路径
//     BFSShortestPath(&G, 0); // 从顶点 A 开始
//
//     return 0;
// }